# coding=utf-8
class page:
    def __init__(self, num, time):
        self.num = num
        self.time = time


class main:
    def __init__(self, a, size):
        self.lv = 0
        self.ci = 0
        self.M = size
        self.N = len(a)
        self.arr_int = a
        self.res = ""
        self.que = ""
        # 当前内存情况
        self.b = [page(-1, self.M - i - 1) for i in range(0, self.M)]
        # M * N 的 -1
        self.c = [[-1 for i in range(0, self.N)] for j in range(0, self.M)]
        self.queue = []
        # k 指向队列的最后一个
        self.k = -1
        # 要替换页的内存索引
        self.flag = -1
        self.process()

    def equation(self, fold, b):
        for i in range(0, self.M):
            if fold == b[i].num:
                return i
        return -1

    def fifo(self, fold, b):
        # 看内存块中是否有此页 即查快表看是否需要产生缺页中断
        val = self.equation(fold, b)
        if val >= 0:
            pass
        else:
            self.queue.append(fold)
            self.k += 1
            self.flag += 1
            self.flag %= self.M
            self.b[self.flag].num = fold

    def Myprint(self, a):
        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"

        for j in range(0, self.N):
            self.res = self.res + "|%5d" % (a[j]) + " "
        self.res = self.res + '|\n'

        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"

        for i in range(0, self.M):
            for j in range(0, self.N):
                if self.c[i][j] == -1:
                    # % 运算符时将 32 替换到格式化字符串中的 %c 占位符
                    self.res = self.res + "|%5c" % 32 + " "
                else:
                    self.res = self.res + "|%5d" % (self.c[i][j]) + " "
            self.res = self.res + "|\n"

        self.res = self.res + "|------"
        for j in range(0, self.N - 2):
            self.res = self.res + "+------"
        self.res = self.res + "+------|\n"

        # k 最开始赋值为 -1 需要额外加 1
        self.ci = self.k + 1
        self.lv = float((self.k + 1) / self.N)

    def print_que(self):
        for i in range(0, self.k + 1):
            self.que = self.que + "%d " % (self.queue[i])

    def process(self):
        a = self.arr_int
        # 遍历每个页
        for i in range(0, self.N):
            # 检查是否缺页 缺页则调度
            self.fifo(a[i], self.b)
            # self.c[0][i] = a[i]
            # 按照每个内存块列赋值当前内存的实时情况 self.b
            for j in range(0, self.M):
                self.c[j][i] = self.b[j].num
        self.Myprint(a)
        self.print_que()

    def get_res(self):
        return self.res

    def get_que(self):
        return self.que

    def get_lv(self):
        return self.lv

    def get_ci(self):
        return self.ci


class FIFO:
    def __init__(self, page_sequence, memory_size):
        """
        初始化FIFO算法
        :param page_sequence: 页面访问序列
        :param memory_size: 内存块数
        """
        self.page_sequence = page_sequence
        self.memory_size = memory_size
        
    def run(self):
        """
        执行FIFO算法
        :return: (缺页次数, 缺页率, 详细步骤)
        """
        memory = []  # 内存状态
        fault_count = 0  # 缺页次数
        detailed_steps = []  # 详细步骤记录
        
        for i, page in enumerate(self.page_sequence):
            # 记录当前步骤前的内存状态
            current_memory = memory.copy()
            
            if page not in memory:
                fault_count += 1
                if len(memory) >= self.memory_size:
                    # FIFO: 移除最先进入的页面
                    removed_page = memory.pop(0)
                else:
                    removed_page = None
                memory.append(page)
                page_fault = True
            else:
                removed_page = None
                page_fault = False
                
            # 记录此步骤的详细信息
            step_info = {
                'step': i + 1,
                'page': page,
                'memory_before': current_memory,
                'memory_after': memory.copy(),
                'page_fault': page_fault,
                'removed_page': removed_page
            }
            detailed_steps.append(step_info)
            
        # 计算缺页率
        fault_rate = (fault_count / len(self.page_sequence)) * 100
        
        return fault_count, fault_rate, detailed_steps


if __name__ == "__main__":
    main([1, 2, 3, 2, 1, 2, 3, 1, 2, 3, 4, 5, 2, 1, 2, 3, 4, 2, 1, 3, 2, 1, 4, 2, 3, 1, 2, 1, 2, 3, 2, 1, 4, 1, 2, 3, 2,
          1, 1, 2, 4, 1, 2, 3, 4, 1, 2, 5, 3, 1, 4, 7, 2, 5, 6, 4, 1, 2, 5, 2], 20)
